package com.algorithm.tuling.zhaoyun.t09.greedy;

import java.util.Scanner;
import java.util.Stack;

/**
 5kg的袋子
 物品：
 钱：6  10  12
 Kg：1  2   4

 我们把5kg的袋子，拆分成1kg，1kg这样子计算，里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品

            1kg	2kg	3kg	4kg	5kg
 加入物品1	6	6	6	6	6
 加入物品2	6	10	10+6=16	10+6=16	16
 加入物品3	6	10	16	16	18


 加入物品2时，袋子当前为1kg 的容量时，我们发现物品2装不进去。那我们应该取多少呢？是不是只要取物品进来时1kg最大钱？，当袋子为2kg时，我们发现物品2可以装下去，此时可以得到10块钱，之前物品1进来时2kg最大是6吧，那我们肯定要选择大的这个10，而不是6.此时袋子还剩0kg可以装。

 袋子为3kg时，我们还是可以装下这个物品2,得到10块，袋子还剩下1kg。
 10+1kg能装的东西。
 物品3来了，袋子为4kg时，物品3可以转进来，得到12块钱，袋子还剩0kg。
 我发现我不装物品3 还能得到16呢
 物品3来了，袋子为5kg时，物品3可以转进来，得到12块钱，袋子还剩1kg。那么装了物品3就能得到12+6=18块钱
 我发现我不装物品3 能得到16，比18小，所以决定装。

 上面这一个递推过程总结起来就是一个东西------状态转移方程：
 能装的时候 每次和上面的比较，大我就装，否则就不装。
 Max(money[i]+res[i-1][w-weight[i]],res[i-1][w]);

 money[i]+res[i-1][w-weight[i]]:装这个物品
 w-weight[i] :表示装完还剩下的空间
 res[i-1][w-weight[i]]:表示装完后剩下的空间还能装的最大值，取上一次的结果。
 Res[i-1][w]表示不装这个物品的值

 */
public class FYDp {
    public static void main(String[] args) {
        /**
         *                  1kg	2kg	3kg	4kg	5kg
         *  加入物品1(1,6)	6	6	6	6	6
         *  加入物品2(2,10)	6	10	10+6=16	10+6=16	16
         *  加入物品3(4,12)	6	10	16	16	18
         */
        int m=0;//m个物品
        int n=0;//最大容量
        int max = 0;//最大价值
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        int [] mArr = new int[m];//每个物品对应的容量
        int [] vArr = new int[m];//每个物品对应的价值
        for(int i=0;i<m;i++){
            mArr[i] = scanner.nextInt();
        }
        for(int i=0;i<m;i++){
            vArr[i] = scanner.nextInt();
        }
        int[][] arr = new int[m+1][n+1];
        for(int i=1;i<=m;i++){//每次加的物品
            for(int j=1;j<=n;j++){//背包总容量分割
                if(mArr[i-1]<=j){//第i个物品能放入背包容量为j
                    //装入i物品时：i物品的价值 + 背包减去i物品的容量能装入的容量时的价值  vArr[i-1] + arr[i-1][j-mArr[i-1]]
                    //不装入i物品时：arr[i-1][j]
                    arr[i][j] = Math.max(vArr[i-1] + arr[i-1][j-mArr[i-1]], arr[i-1][j]);
                }else{
                    arr[i][j] = arr[i-1][j];//不能装入，把i物品之前的容量移动下来
                }
            }
        }
        //算出哪些物品
        /**
         * 从右下角算起，如果当前物品i对应的总价值  和  i-1 对应的总价值 相等，说明i没有加入
         * 如果不相等，说加入了；此时需要背包容量减去i对应的容量，再进行计算
         */
        Stack<Integer> stack = new Stack<>();
        int j = n;
        for(int i = m ; i>=1; i--){
            if(arr[i][j] != arr[i-1][j]){
                //i加入
                stack.push(i);
                j = j - mArr[i-1];
            }
        }
        max = arr[m][n];
        System.out.println(max);
        System.out.println(stack);

    }
}
